1. Technical Field of the Invention
The present invention relates in general to the field of computer processors.
2. Description of the Related Art
Picking free (or unused) entries out of a set of entries in a queue is a common task within computer processors. One example is of a processor picking free entries in a queue is register renaming. Machine language programs specify reads and writes to a limited set of registers specified by the instruction set architecture (ISA) of processor. The registers specified by the ISA are the architectural registers. For example, if the ISA of the processor specifies 8 registers in the instruction set, programs written processor will specify operations reading from and writing to those 8 registers. Modern processors, however, are often designed with more physical registers than there are architectural registers specified in the ISA to achieve additional parallelism. Having more physical registers can prevent bottlenecks within a processor and enables faster instruction execution. Instead of waiting for a register specified in the instruction to become available, the processor can use one of the additional physical registers to execute in the instruction in parallel (e.g., “out-of-order” execution). Utilizing the extra physical registers in a processor requires a technique known as register renaming, whereby architectural registers are mapped to physical registers. Logic within the processor performs register renaming, which frequently requires identifying multiple free physical registers in a register file available for mapping to architectural registers.
Picking multiple unused registers at once (in parallel) is difficult because preventing the same register from being picked twice causes a serialization of the process, which results in slower instruction execution. For example, logic within the processor picks the first unused register in a register file for register renaming. Then, from the new set of unpicked registers, the logic picks another register until all needed registers are picked. Such a serialized process requires more time to complete than a process that can take place in parallel. A typical solution to serialization is to restrict each pick to a subset of the registers in the register file in order to ensure that one register isn't picked twice in parallel. The problem with this approach is that an individual subset might not have any unused registers, causing the operation to fail, while another subset might have multiple unused registers.